BZOJ3157 国王奇遇记 <倍增>

Problem

国王奇遇记

Description

Input

共一行，包括两个正整数和。

Output

共一行，为所求表达式的值对取模的值。

Sample Input

5 3

Sample Output

Hint

，

Source

标签：倍增

Solution

倍增处理幂和。
令

则

于是可以将规模为的问题根据奇偶性降低到规模为和的问题，递归处理即可。

加强版见BZOJ3516，加强版之再加强版见BZOJ4126。

Code

#include <bits/stdc++.h>
#define MX 200
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m; lnt f[60][MX+5], p[MX+5], fac[MX+5], inv[MX+5];
void init() {
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= MX; i++) fac[i] = fac[i-1]*i%P;
    for (int i = 2; i <= MX; i++) inv[i] = (P-P/i*inv[P%i]%P)%P;
    for (int i = 2; i <= MX; i++) inv[i] = inv[i-1]*inv[i]%P;
}
lnt Pow(lnt x, int k) {
    lnt ret = 1;
    for (; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
lnt C(int n, int m) {return fac[n]*inv[m]%P*inv[n-m]%P;}
void calc(int n, int stp) {
    if (!n) return;
    if (n&1) {
        calc(n-1, stp+1);
        for (int i = 0; i <= m; i++) f[stp][i] = m;
        for (int i = 0; i <= m; i++) for (int j = 0; j <= i; j++)
            f[stp][i] = (f[stp][i]+m*C(i, j)%P*f[stp+1][j]%P)%P;
    } else {
        calc(n/2, stp+1); lnt pw = Pow(m, n/2); p[0] = 1;
        for (int i = 1; i <= m; i++) p[i] = p[i-1]*(n/2)%P;
        for (int i = 0; i <= m; i++) f[stp][i] = f[stp+1][i];
        for (int i = 0; i <= m; i++) for (int j = 0; j <= i; j++)
            f[stp][i] = (f[stp][i]+pw*C(i, j)%P*p[i-j]%P*f[stp+1][j]%P)%P;
    }
}
int main() {
    read(n), read(m);
    init(), calc(n, 0);
    printf("%lld\n", f[0][m]);
    return 0;
}